#include <bits/stdc++.h>

using namespace std;

class Solution_no_1 {
public:
    //遍历，然后找出最小的几个
    //时间超限
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        int len=arr.size();
        vector<int> m_heap;
        if(k<=0||k>len) return m_heap;
        if(k==len) return arr;

        for(int i=0;i<len;i++){
            int tmp=m_heap.size();
            if(tmp<k){
                m_heap.push_back(arr[i]);
                make_heap(m_heap.begin(),m_heap.end(),less<int>());
            }else{
                if(arr[i]< m_heap[0]){
                    m_heap[0]=arr[i];
                    make_heap(m_heap.begin(),m_heap.end(),less<int>());
                }
            } 
        }
        return m_heap;
    }
};
class Solution_no_2 {
public:
    //遍历，然后找出最小的几个
    //时间超限
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        int len=arr.size(),m_size=0;
        vector<int> m_arr;
        if(k<=0||k>len) return m_arr;
        if(k==len) return arr;

        for(int i=0;i<len;i++){
            m_size=m_arr.size();
            if(m_size<k){
                m_arr.push_back(arr[i]);
            }else{
                sort(m_arr.begin(),m_arr.end());
                if(arr[i]<m_arr[k-1]){
                    m_arr[k-1]=arr[i];
                }
            }
        }
        return m_arr;
    }
};
class Solution1 {
    vector<int> ans;
public:
    //利用快排进行切分
    //过了 92 ms
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> m_arr;
        int len=arr.size();
        if(k<=0||k>len) return m_arr;
        if(k==len) return arr;
        ans.clear();
        return quick(arr,0,len-1,k);
    }
    vector<int> quick(vector<int>& arr, int low,int high,int k){
        int x=par(arr,low,high);
       
        if(x==k){
            for(int i=0;i<=k-1;i++) ans.push_back(arr[i]);
            return ans;
        }
        return x>k ? quick(arr,low,x-1,k):quick(arr,x+1,high,k);
    }
    int par(vector<int> &arr,int l,int r){
        int k=arr[l];
        int i=l,j=r;
        while(i<j){
            while(i<j && arr[j] >= k) j--;
            arr[i]=arr[j];
            while(i<j && arr[i]<= k) i++;
            arr[j]=arr[i];
        }
        arr[i]=k;
        return i;
    }

};

class Solution {
    vector<int> ans;
public:
    //利用priority_queue 实现，比我自己用堆效率高？
    // 116 ms??我自己的就不行？
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> m_arr;
        int len=arr.size();
        if(k<=0||k>len) return m_arr;
        if(k==len) return arr;
        ans.clear();
        priority_queue<int,vector<int>,less<int> > pq;
        for(int i=0;i<len;i+=1){
            if(pq.size()<k){
                pq.push(arr[i]);
            }else if(arr[i]<pq.top()){
                pq.pop();
                pq.push(arr[i]);
            }
        }
        ans.clear();
        while(!pq.empty()){
            ans.push_back(pq.top());
            pq.pop();
        }
        return ans;
    }
    

};

int main(){
    vector<int> v={3,2,1};
    Solution s;
    vector<int> vv=s.getLeastNumbers(v,2);
    for(int i=0;i<vv.size();i++){
        cout << vv[i] << " ";
    }cout << endl;



    return 0;
}